Voicemail is a popular telephone service feature, and is often included in the price paid for telephone service. When a called line with voicemail functionality does not answer or is busy, a call can be handled by a voicemail system. A voicemail system can store recordings and/or announcements for a user. When a call is passed to a voicemail system, the voicemail system can play one or more recordings and/or announcements for the calling party, or a generic message, and can prompt the calling party to leave a message, for example, a spoken message. The voicemail system can record the calling party's message and store the message, for example, as audio data in a storage device. Call data associated with the message, for example, the calling party's telephone number, the date and time of the call, and the like, can also be stored by the voicemail system and associated with the stored message. Some voicemail systems also allow calling parties to leave alphanumeric messages for a called party. In any event, the voicemail system can store the message and/or data and associated call data.